package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * 72. 编辑距离
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/21 14:24
 */
public class MinDistance72 {
    public int minDistance(String word1, String word2) {
        int l1 = word1.length();
        int l2 = word2.length();
        if ("".equals(word1)) {
            return l2;
        }
        if ("".equals(word2)) {
            return l1;
        }
        char[] cs1 = word1.toCharArray();
        char[] cs2 = word2.toCharArray();
        int[] dp = new int[l2 + 1];
        for (int i = 0; i <= l2; i++) {
            dp[i] = i;
        }
        int sum;
        int item;
        for (int i = 1; i <= l1; i++) {
            item = dp[0];
            dp[0] = i;
            for (int j = 1; j <= l2; j++) {
                sum = dp[j];
                if (cs1[i - 1] == cs2[j - 1]) {
                    dp[j] = item;
                } else {
                    dp[j] = Math.min(Math.min(item, dp[j - 1]), dp[j]) + 1;
                }
                item = sum;
            }
        }
        return dp[l2];
    }
}
